/*******************************************
Module: zt_tree_redblack.h
E-Mail: 24zhutian@gmail.com
Notices: Copyright (c) 2007-2011 ls
*******************************************/
#ifndef zt_tree_redblack_h
#define zt_tree_redblack_h

#ifdef __cplusplus
extern "C" {
#endif

typedef struct zt_tree_redblack_node_s{
	unsigned int key;
	void *data;

	unsigned char color;	/* if color=0 then the node is black */

	struct zt_tree_redblack_node_s *left;
	struct zt_tree_redblack_node_s *right;
	struct zt_tree_redblack_node_s *parent;
}zt_tree_redblack_node;

typedef struct zt_tree_redblack_s{
	zt_tree_redblack_node *root;
	zt_tree_redblack_node *nil;
}zt_tree_redblack;

#define ZT_TREE_RB_RED(n)		((n)->color=1)
#define ZT_TREE_RB_BLACK(n)		((n)->color=0)
#define ZT_TREE_RB_ISRED(n)		((n)->color)
#define ZT_TREE_RB_ISBLACK(n)	(!ZT_TREE_RB_ISRED(n))
#define ZT_TREE_RB_CPYCOLOR(d,s) ((d)->color=(s)->color)

#define ZT_TREE_RB_LT(a,b)		((a)<(b))
#define ZT_TREE_RB_GT(a,b)		((a)>(b))
#define ZT_TREE_RB_EQ(a,b)		((a)==(b))

ZT_API void zt_tree_redblack_init(zt_tree_redblack *t,zt_tree_redblack_node *nil);

ZT_API zt_tree_redblack_node* zt_tree_redblack_insert(zt_tree_redblack *t,zt_tree_redblack_node *n);
ZT_API void zt_tree_redblack_delete(zt_tree_redblack *t,zt_tree_redblack_node *n);

ZT_API zt_tree_redblack_node* zt_tree_redblack_query(zt_tree_redblack *t,unsigned int k);
ZT_API zt_tree_redblack_node* zt_tree_redblack_min(zt_tree_redblack *t);
ZT_API zt_tree_redblack_node* zt_tree_redblack_max(zt_tree_redblack *t);

ZT_API void zt_tree_redblack_order(zt_tree_redblack *t,void (*ZT_TREE_REDBLACK_CALLBACK)(zt_tree_redblack_node *));

#ifdef __cplusplus
}
#endif /* C++ */
#endif /* zt_tree_redblack_h */
